In a system that shares resources, there is at least one server end to provide service and a plurality of client ends which selectively receives such services. A client end receives such services by transmitting a request, having the appropriate protocol, to the server end for accessing the resources provided by the system, over, e.g., a shared communication channel in a network system. For example, a media-on-demand network system may comprise a media server connected to a plurality of clients over a shared transmission medium.
Of course, a system with shared resources has an inherent limit on the services it provides. For example, when there are too many communication requests in the system, not all of the requests submitted by the clients can be satisfied. This is especially true when the received communication requests require a minimum quality-of-service (QoS) criteria or support real time communication services. That is, for a server to support real-time media, the server typically integrates various types of QoS criteria within one system framework. For example, in an asynchronous transfer mode (ATM) system, the QoS sets the tolerances, i.e., performance requirements, for the data packet cell loss ratio, the cell transfer delay, and the delay jitter.
Accordingly, to provide for such QoS and real time communication services, an admission controller may be provided to allocate the system's limited resources efficiently. In other words, the purpose of an admission controller is to ensure that the system can provide the appropriate QoS criteria to all the admitted requests, i.e., received requests having the correct protocol. The admission controller can check all the requests in the system to ensure that all requests receive the predefined quality of service criteria. In addition, the admission controller can check each admitted request to determine if it will have a so called "pushing effect" on the existing requests which might affect their QoS. In terms of actual application, as long as the admission controller checks every newly submitted request from the time the system starts, it can be ensured that all the admitted requests will be within the minimum QoS criteria.
The operation of the admission controller can be best described with reference to FIG. 1. FIG. 1 shows a constant bit rate system (CBR) which uses evenly divided slots as its transmission method to transmit fixed length packets. In FIG. 1, there are m number of users who share one resource item z, with an admission controller 5 controlling and assigning the slots to each user. However, the priority of each connection must be determined using, for instance, a rate monotonic algorithm which follows static priority assignment rules. This assignment rule is described as follows. When D.sub.i .ltoreq.D.sub.j, the priority of the i.sup.th connection is greater than the priority of the j.sup.th connection. Here, D.sub.i stands for the cycle of the refers to the number of time slots that has to pass before a fixed length packet is sent out by the i.sup.th connection in a continuous time slot system. For instance, when the cycle of the i.sup.th is 4, it means that this connection will send out a fixed length packet every 4 time slots. The rate monotonic rule mentioned hereinabove can be simply described as follows the greater the cycle of a connection is, the lower its priority will be; the smaller the cycle of a connection is, the higher its priority will be. In FIG. 1, if the connections are assumed to have been arranged in order of the cycles, all the connections can be presented as: EQU D.sub.1 .ltoreq.D.sub.2 .ltoreq. . . . .ltoreq.D.sub.m.
In the system, if the packet issued by a connection can be served before the next packet arrives, then the current system is then capable of accepting requests of all connections D.sub.1 -D.sub.m. When the system is capable of accepting requests from all connections, the system is said to be "schedulable". This schedulability can thus be used by the network access admission controller in determining if the system can provide real time service to all current and newly admitted connections. The relationship between schedulability and admission control can be described as follows. If a request for a new connection is received and it is determined that the new connection plus all current connections can still meet the requirements of schedulability (defined above), then the admission controller can accept the request of this new connection because the packets issued by all the connections will be processed before the next packet is sent out, in which situation real time transmission is made possible. On the other hand, when schedulability is not possible, the admission controller indicates that some connections will be affected by the admission of the new connection. In other words, the connections will not receive the required service standard and the admission controller therefore will reject the request of this new connection. In short, the basic rule of determination used by the admission controller is the schedulability of a connection.
The method of determining the schedulability of the requests is to allow all the connections send out their request packets simultaneously. The rule of determining the schedulability is as follows. D.sub.1, . . . , m is schedulable if and only if packet P.sub.k will be served no later than the D.sub.k.sup.th time slot, where 1.ltoreq.k.ltoreq.m.
In other words, when all the connections send out a packet simultaneously, any one of these packets must be processed with in the cycle of its corresponding connection (namely before the next packet is issued). If this limit is crossed, there is clearly an indication that the requirements cannot be satisfied when the system is at its maximum capacity (namely, when all the connections sere not schedulable.
To implement the rule of determination described hereinabove, it is necessary to convert it to some quantifiable format that can be used in actual applications. In U.S. Pat. No. 5,528,513 entitled, "Scheduling and Admission Control Policy for a Continuous medai Server" by Vaitzblit et al and in IEEE Infocom '96 article entitled, "Traffic-Controlled Rate-Monotonic Priority Scheduling of ATM Cells" by Seok-Kyu and Kang G. Shin, for instance, this rule of determination is essentially converted to: ##EQU1## where .left brkt-top.x.right brkt-top. represents the smallest integer greater than or equal to x.
Using this rule of conventional admission control, correct schedulable can be determined in most cases. However, the "if and only if" condition in the above rule does not always work. Therefore, a wrong determination is possible under certain circumstances. The following example is cited to show a situation where the system is schedulable although it is determined otherwise using the conventional rule of determination for schedulability previously described.
In this example, the number of connections is 4, and the cycles of a ll connections are D.sub.1 . . . .sub.4 =4,4,4,5!. When the conventional rule of determination is used to determine the schedulability of the 4.sup.th connection (its cycle equals 5), the result is: ##EQU2## This result indicates that the system is not schedulable according to the conventional rule of determination. However in reality, this system is schedulable as confirmed by the rate monotonic rule of assignment described below.
FIG. 2 illustrates the schedulability of the system with the cycles of D.sub.1 . . . 4 =4,4,4,5! using the rate monotonic rule of assignment. In this figure, the communication channels of the system are simulated to be the continuous time slots S1-S17 The cycles of the first, the second, and the third connections all have a cycle of 4 for the packets which are represented by the symbols of a, b, and c respectively. The cycle of the packet by the fourth connection is 5 and the packet is represented by the symbol of d.
It is assumed that all the connections issue their packets simultaneously before the time slot S1. During time slot S1, the smaller the cycle is, the higher its priority will be, according to the rule of assignment. Thus, packet a issued by the first connection is processed in time slot S1. Similarly, packets b and c issued by the second and the third connections are processed in time slots S2 and S3. By this time, all the packets issued by the connections from the first to the third which have higher priorities have been processed already so that time slot S4 can now process the fourth connection which has a lower priority. At this time, all packets have been processed, which fact indicates that the system meets the description of the most basic format of schedulability. In other words, the system is schedulable. However, using the extensions described in the U.S. Pat. No. 5,528,513, the system cannot be correctly determined as schedulable, and accordingly, the conventional technology may generate incorrect determinations.
The actual determination according to the conventional rule of schedulability is directed toward each connection to determine if a packet can be inserted in the last time slot within a cycle. However, in the above-mentioned example, the fourth connection cannot possibly inset any packet in time slot S5 because new packets have already been issued by the first to the third connections and the packet issued by the fourth connection is inserted in the unused time slot S4 to complete the scheduling process. Thus, it is desired to establish a new rule of schedulability to determine if all the connections are schedulable and if the system can still maintain its property of schedulability, via an admissions controller, when a new connection is introduced. On the other hand, a new rule of detection must avoid the errors found in the conventional technology and able to detect all of the time slots. It is also desired to have a simplified computing process for an admission controller which will detect all of the time slots in a given cycle.
Accordingly, it is an object of the present invention to accurately determine the schedulability for network access, while determining the schedulability for connections to efficiently utilize the resources provided by the system.
Another object of the present invention is to include an admission controller that accurately determines the schedulability for network access.
Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description and the novel features which will be particularly pointed out in the appended claims.